This application relates to two applications concurrently filed herewith entitled (1) xe2x80x9cCRYPTOGRAPHIC COMMUNICATION METHOD, ENCRYPTION METHOD, AND CRYPTOGRAPHIC COMMUNICATION SYSTEMxe2x80x9d that claims foreign priority based on Japanese patent applications 10-262035, filed Sep. 16, 1998 and 10-338190, filed Nov. 27, 1998 inventors: Masao Kasahara and Yasuyuki Murakami; Express Mail EL 446 156 915 US) and (2) xe2x80x9cENCRYPTION METHOD, DECRYPTION METHOD, ENCRYPTION/DECRYPTION METHOD, CRYPTOGRAPHIC COMMUNICATIONS SYSTEM, AND COMPUTER USABLE MEDIUMxe2x80x9d that claims foreign priority based on Japanese patent applications 10-262036, filed Sep. 16, 1998 and 11-105815, filed Apr. 13, 1999 inventors: Masao Kasahara and Yasuyuki Murakami; Express Mail EL 446 156 827 US), which applications are hereby incorporated by reference in their entirety.
1. Field of the Invention
This invention relates to an encryption method for converting plaintext into ciphertext, and to a decryption method for converting ciphertext into the original plaintext, and more particularly relates to product-sum type cryptosystem.
2. Description of the Related Art
In today""s world, characterized by sophisticated information utilization, important business document and image information are transmitted and communicated in the form of electronic information over an infrastructure of computer networks. By its very nature, electronic information can be easily copied, making it extremely difficult to distinguish between the copy and the original, and information security has become a very serious problem. The realization of computer networks which support xe2x80x9ccomputer resource sharing,xe2x80x9d xe2x80x9cmulti-accessing,xe2x80x9d and xe2x80x9cwide-area implementationxe2x80x9d is particularly indispensable to the establishment of a high-level information society. However, that very realization involves factors that are in conflict with the goal of information security between involved parties. An effective technique for eliminating those inconsistencies is encryption technology, whichup until now, in the course of human history, has been primarily used in the fields of military operations and foreign diplomacy.
Cryptography is the exchange of information in such a way that the meaning of that information cannot be understood by anyone other than the authorized parties. In cryptography, the conversion of the original text (plaintext), that is understandable by anyone, to a text (ciphertext), the meaning of which is not understood by a third party is called encryption, and the changing of ciphertext into plaintext is decryption. The overall process of this encryption and decryption is called a cryptosystem. In the encryption process and decryption process, respectively, secret data called an encryption key and a decryption keys are employed. Since a secret decryption key is necessary for decryption, only a party who knows that decryption key can decrypt the ciphertext, enabling the confidentiality of the information to be maintained in accordance with encryption.
Generally, there are two types of encryption schemes. Namely common key encryption scheme and public key encryption scheme. In a common key encryption scheme, the encryption key and the decryption key are identical, and cryptographic communication is conducted with the identical keys in the possession of both the sending party and the receiving party. The sending party encrypts plaintext based on the common key and sends it to the receiving party, whereupon the receiving party uses the common key to decrypt the ciphertext into the original plaintext.
By contrast, in a public key encryption scheme, the encryption key and decryption key are different. In conducting cryptographic communications in this system, the sending party encrypts the plaintext with the public key of a receiving party, and the receiving party decrypts that ciphertext with his or her own secret key. The public key is used for encryption, and the secret key is a key for decrypting the ciphertext encrypted by the public key. The ciphertext encrypted by the public key can only be decrypted using a secret key.
New methods for product-sum type cryptosystem, which is one public key encryption scheme, as well as attack methods (methods for breaking the codes), are being proposed one after another. A particularly urgent task is now that of developing cryptographic techniques capable of high-speed decryption so as to enable large volumes of information be processed in short times.
An object of the present invention, which was devised in view of the situation described in the foregoing, is to provide a new encryption method and decryption method for product-sum type cryptosystem wherewith high-speed decryption processing is possible.
Another object of the present invention is to provide an encryption method and decryption method wherewith vulnerability to attack by the LLL (Lenstra-Lenstra-Lovasz) method is minimized and security is enhanced.
According to the first aspect of the present invention, there is provided an encryption method comprising the step of preparing a plaintext vector m=(m0, m1, . . . , mKxe2x88x921) that is obtained by dividing plaintext by K, the step of preparing base vectors D=(D0, D1, . . . , DKxe2x88x921), with Di (0xe2x89xa6ixe2x89xa6Kxe2x88x921) being set to Di=d/di (where d=d0d1 . . . dKxe2x88x921, and any two numbers di and dj are prime relative to each other), and the step of yielding ciphertext C=m0D0+m1D1+ . . . +mKxe2x88x921DKxe2x88x921 from the plaintext vector m and base vectors D.
Random number vectors v=(v0, v1, . . . , vKxe2x88x921) may further be used to yield ciphertext C=m0v0D0+m1v1D1+ . . . +mKxe2x88x921vKxe2x88x921DKxe2x88x921. A plurality of sets each containing K terms of di (i=0, 1, 2, . . . , Kxe2x88x921) elements may be provided, and ciphertext is obtained for each of those sets, respectively.
According to the second aspect of the present invention, there is provided an encryption method comprising the step of preparing a plaintext vector m=(m0, m1, . . . , mKxe2x88x921 that K-divides plaintext, the step of preparing base vectors D=(D0, D1, . . . , DKxe2x88x921), with Di (0xe2x89xa6ixe2x89xa6Kxe2x88x921) being set to Di=(d/di)vi (where d=d0d1 . . . dKxe2x88x921, any two numbers di and dj are prime relative to each other, and vi is a random number), and the step of yielding ciphertext C=m0D0+m1D1+ . . . +mKxe2x88x921DKxe2x88x921 from the plaintext vector m and base vectors D.
A plurality of sets each containing K terms of di (i=0, 1, 2, . . . , Kxe2x88x921) elements may be provided, and ciphertext is obtained for each of those sets, respectively.
According to the third aspect of the present invention, there is provided a decryption method for decrypting the ciphertext C encrypted by any of the above described encryption methods, wherein the plaintext vector m=(m0, m1, . . . , mKxe2x88x921) is found by formula (a) below.
mixe2x89xa1CDixe2x88x921 (mod di)xe2x80x83xe2x80x83(a)
According to the fourth aspect of the present invention, there is provided an encryption/decryption method comprising the steps of:
providing a plaintext vector m=(m0, m1, . . . , mKxe2x88x921) that K-divides plaintext;
providing base vectors D=(D0) D1, . . . , DKxe2x88x921), with Di (0xe2x89xa6ixe2x89xa6Kxe2x88x921) being set to d/di, using the integer di, (where d=d0d1 . . . dKxe2x88x921, and any two numbers di and dj are prime relative to each other);
selecting w to satisfy w less than P (P=prime number), and finding a public key vector c=(c0, c1, . . . , cKxe2x88x921) from formula (b),
cixe2x89xa1wDi (mod P)xe2x80x83xe2x80x83(b);
producing the ciphertext C indicated in formula (c) from the inner product of a plaintext vector m and public key vector c,
C=m0c0+m1c1+ . . . +mKxe2x88x921cKxe2x88x921xe2x80x83xe2x80x83(c);
finding intermediate decrypted text M for the ciphertext C from formula (d),
Mxe2x89xa1wxe2x88x921C (mod P)xe2x80x83xe2x80x83(d);
finding the plaintext vector m=(m0, m1, . . . , mKxe2x88x921) by decrypting that intermediate decrypted text M by formula (e) below,
mixe2x89xa1MDi1 (mod di)xe2x80x83xe2x80x83(e); and
obtaining the original text from the plaintext vector m.
According to the fifth aspect of the present invention, there is provided an encryption/decryption method comprising the steps of:
providing a plaintext vector m=(m0, m1, . . . , mKxe2x88x921) that K-divides plaintext;
providing base vectors D=(D0, D1, . . . , DKxe2x88x921), with Di (0xe2x89xa6ixe2x89xa6Kxe2x88x921) being determined by equation (f),
Di=(d/di) vixe2x80x83xe2x80x83(f)
where
vi is a random number,
di is an integer, and
d=d0d1 . . . dKxe2x88x921 
and where any two integers di and dj are prime relative to each other);
selecting w to satisfy w less than P (P=prime number), and finding a public key vector c=(c0, c1, . . . , cKxe2x88x921) from formula (g),
cixe2x89xa1wDi (mod P)xe2x80x83xe2x80x83(g);
producing the ciphertext C indicated in formula (h) from the inner product of a plaintext vector m and public key vector
xe2x80x83C=m0c0+m1c1+ . . . +mKxe2x88x921cKxe2x88x921xe2x80x83xe2x80x83(h);
finding intermediate decrypted text M for ciphertext C from formula (i),
Mxe2x89xa1wxe2x88x921C (mod P)xe2x80x83xe2x80x83(i);
finding the plaintext vector m=(m0, m1, . . . , mKxe2x88x921) by decrypting that intermediate decrypted text M by formula (j) below,
mixe2x89xa1MDixe2x88x921 (mod di)xe2x80x83xe2x80x83(j); and
obtaining the original plaintext from the plaintext vector m.
According to the sixth aspect of the present invention, there is provided an encryption/decryption method comprising the steps of:
providing a plaintext vector m=(m0, m1, . . . , mKxe2x88x921) that K-divides plaintext;
providing prime numbers P and Q;
providing a base vector D (D0, D1, . . . , DKxe2x88x921) with DPi (0xe2x89xa6ixe2x89xa6Kxe2x88x921) satisfying DPi=dP/dPi, using the integer dPi, (where dP=dP0dP1 . . . dPKxe2x88x921; and any two numbers dPi and dPj are prime relative to each other);
providing another base vector D=(D0 D1, . . . , DKxe2x88x921) with DQi (0xe2x89xa6ixe2x89xa6Kxe2x88x921) satisfying DQi=dQ/dQi, using the integer dQi, (where dQ=dQ0dQ1 . . . dQKxe2x88x921, and any two numbers dQi and dQj are prime relative to each other);
deriving a minimum integer Di such that remainders resulting by P and Q become DPi and DQi, respectively, using the Chinese remainder theorem;
selecting w to satisfy w less than N (N=PQ), and finding a public key vector c=(c0, c1, . . . , cKxe2x88x921) from formula (k),
cixe2x89xa1wDi (mod N)xe2x80x83xe2x80x83(k);
producing the ciphertext C indicated in formula (l) from the inner product of a plaintext vector m and public key vector c,
C=m0c0+m1c1+ . . . +mKxe2x88x921cKxe2x88x921xe2x80x83xe2x80x83(l)
finding intermediate decrypted text MP and MQ, with modulus P and modulus Q, for the ciphertext C, as in formulas (m) and (n),
MPxe2x89xa1wxe2x88x921C (mod P)xe2x80x83xe2x80x83(m),
MQxe2x89xa1wxe2x88x921C (mod Q)xe2x80x83xe2x80x83(n),
finding a pair of remainders (mi(P), mi(Q)) by decrypting the intermediate decrypted-text MP and MQ by formulas (o) and (p) below,
mi(P)xe2x89xa1MPDPixe2x88x921 (mod dPi)xe2x80x83xe2x80x83(o),
mi(Q)xe2x89xa1MQDQixe2x88x921 (mod dQi)xe2x80x83xe2x80x83(p);
applying the Chinese remainder theorem to mi(P) and mi(Q) to find the plaintext vector m=(m0, m1, . . . , mKxe2x88x921); and
obtaining the original plaintext from the plaintext vector m.
The ciphertext C may be sent with the N as modulus.
According to seventh aspect of the present invention, there is provided a cryptographic communications system for conducting information communications between a plurality of entities using ciphertext, comprising: an encryptor for producing ciphertext from plaintext using any one of the above described encryption methods; a communication path for transmitting the produced ciphertext from one entity to another entity or entities; and a decryptor for decrypting transmitted ciphertext to the original plaintext.
According to the eighth aspect of the present invention, there is provided an encryption method for obtaining ciphertext from components of a plaintext vector and components of one of multiple types bf base vectors, wherein the ciphertext is generated containing information indicative of which base vector (or vector component(s)) has been used. The plaintext vector is obtained by dividing the plaintext.
According to the ninth aspect of the present invention, there is provided an encryption method for obtaining ciphertext from plaintext, comprising the steps of:
providing a plaintext vector m=(m1, m2, . . . , mKxe2x88x921) that (Kxe2x88x921)-divides the plaintext;
providing first base vectors DP=(DP0, DP1, . . . , DPKxe2x88x921) which is set to DPi=dP0dP1 . . . dPKxe2x88x921/dPi with integers dPi (0xe2x89xa6ixe2x89xa6Kxe2x88x921) and second base vectors DQ=(DQ0, DQ1, . . . , DQKxe2x88x921) which is set to DQi=dQ0dQ1 . . . dQKxe2x88x921/ddQi with integers dQi (0xe2x89xa6ixe2x89xa6Kxe2x88x921);
discretionarily selects either DPi or DQi as Di; and
obtaining ciphertext c=m0D0+m1D1+ . . . +mKxe2x88x921DKxe2x88x921 with m0 indicating DPi/DQi selection information.
According to the tenth aspect of the present invention, there is provided a decryption method for decrypting the ciphertext C encrypted by the encryption method described just above, wherein components of the plaintext vector m forming products with DPi in the ciphertext C and the m0 are decrypted; and components of the plaintext vector m forming products with DQi in the ciphertext C are next decrypted.
The concept of the encryption and decryption methods of the present invention is now described.
Let a set {di} be considered which contains K integer elements. Arbitrary two integer elements among this set are prime. The product of these K elements is represented by d, as given in equation (1) below, and the base Di is defined as in equation (2).
d=d0d1 . . . dKxe2x88x921xe2x80x83xe2x80x83(1)
Di=d/dixe2x80x83xe2x80x83(2)
Now, a message m=(m0, m1, . . . , mKxe2x88x921) is represented as given in equation (3) below, using the base D=(D0, D1, . . . , DKxe2x88x921).
M=m0D0+m1D1+ . . . +mKxe2x88x921DKxe2x88x921xe2x80x83xe2x80x83(3)
Here, the elements mi in the message vector m are set so as to satisfy mi less than di.
In the present invention, ciphertext is produced in this manner, that is, using equations (1) to (3).
When the base is given by equation (2), the message m=(m0, m1, . . . , mKxe2x88x921) can be decrypted from the integer M using the algorithm noted below. This decryption algorithm is called a parallel decryption algorithm.
Parallel Decryption Algorithm
unit i (mi decryption)
mixe2x89xa1MDixe2x88x921 (mod di)
Encryption techniques based on this concept and the decryption methods therefor are subject matters of the present invention. The specific techniques are described subsequently.
With the present invention, moreover, a plurality of types of base vector are provided, and the ciphertext C=m0D0+m1D1+ . . . +mKxe2x88x921DKxe2x88x921 is produced using a plaintext vector m=(m1, m2, . . . , mKxe2x88x921 that divides the plaintext to be encrypted, a base vector D=(D0, D1, . . . , DKxe2x88x921) configured by selecting the i""th component Di (0xe2x89xa6ixe2x89xa6Kxe2x88x921) from any one of the plurality of types of base vector, and m0 indicating which base vector was selected to provide the i""th components. Thus, while it is easy for an authorized decrypting party to determine which base vector""s components Di have been selected based on the decrypted m0 information, it is extremely difficult for an attacking party to find out which base vector""s components Di have been selected, whereupon attack by the LLL method is made exceedingly difficult. As a consequence, security is enhanced.